package parser;

import ic.ast.BinaryOp;
import ic.ast.Call;
import ic.ast.ClassType;
import ic.ast.DeclClass;
import ic.ast.DeclField;
import ic.ast.DeclLibraryMethod;
import ic.ast.DeclMethod;
import ic.ast.DeclStaticMethod;
import ic.ast.DeclVirtualMethod;
import ic.ast.Expression;
import ic.ast.Length;
import ic.ast.Literal;
import ic.ast.LocalVariable;
import ic.ast.New;
import ic.ast.NewArray;
import ic.ast.NewInstance;
import ic.ast.Node;
import ic.ast.Parameter;
import ic.ast.PrimitiveType;
import ic.ast.Program;
import ic.ast.Ref;
import ic.ast.RefArrayElement;
import ic.ast.RefField;
import ic.ast.RefVariable;
import ic.ast.Statement;
import ic.ast.StaticCall;
import ic.ast.StmtAssignment;
import ic.ast.StmtBlock;
import ic.ast.StmtBreak;
import ic.ast.StmtCall;
import ic.ast.StmtContinue;
import ic.ast.StmtIf;
import ic.ast.StmtReturn;
import ic.ast.StmtWhile;
import ic.ast.This;
import ic.ast.Type;
import ic.ast.UnaryOp;
import ic.ast.VirtualCall;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

import lex.Token;
import fun.grammar.Grammar;
import fun.grammar.Word;
import fun.parser.earley.EarleyParser;
import fun.parser.earley.EarleyState;

/**
 * 
 * The parser object will parse any of the two given grammar types. It will
 * process any expression in the IC language and use prettyPrint() to show its
 * output
 * 
 */
public class Parser {

	/*
	 * Grammars for either program or library cases S is the start symbol and
	 * every newline is a derivation rule
	 */

	private String libGrammar = "S -> icLibGrammar\n"
			+ "icLibGrammar -> class CLASS_ID { libraryMethod }\n"
			+ "libraryMethod -> | optionalLibraryMethods libraryMethod\n"
			+ "optionalLibraryMethods -> static returnType ID ( formalArgs ) ;\n"
			+ "returnType -> type | void\n"
			+ "formalArgs -> | type ID optionalFormalArgs\n"
			+ "optionalFormalArgs -> | , type ID optionalFormalArgs\n"
			+ "type -> type [ ] | int | boolean | string | CLASS_ID\n";

	private String nonLibGrammar = "S -> program\n"
			+ "program -> classDecl program | classDeclExtendsSuperClass program | \n"
			+ "classDecl -> class CLASS_ID { classSArgs }\n"
			+ "classDeclExtendsSuperClass -> class CLASS_ID extends CLASS_ID { classSArgs }\n"
			+ "classSArgs -> | fields classSArgs | methods classSArgs\n"
			+

			"type -> type [ ] | int | boolean | string | CLASS_ID\n"
			+ "fields -> type ID optionalFields ;\n"
			+ "optionalFields -> | , ID optionalFields\n"
			+

			"methods -> dynOrStatic returnType ID ( formalArgs ) { optionalStatements }\n"
			+ "dynOrStatic -> | static\n"
			+ "formalArgs -> type ID optionalFormalArgs | \n"
			+ "optionalFormalArgs -> | , type ID optionalFormalArgs\n"
			+ "returnType -> type | void\n"
			+

			"statement -> innerInnerIfOptionForNoIf | innerIf\n"
			+ "statementWithoutIfDec -> refToValue = expression ; | methodCall ; | return retVal ; | myWhile | break ; | continue ; | { optionalStatements }\n"
			+ "optionalStatements -> | statement optionalStatements\n"
			+ "statementDecl -> type ID optionalInitialization ;\n"
			+ "optionalInitialization -> | = expression\n"
			+

			"refToValue -> ID | fieldOrArrRef . ID | fieldOrArrRef [ expression ]\n"
			+ "expressionWithoutBinaryOp -> refToValue | methodCall | this | ( expression ) | literal | fieldOrArrRef . length\n"
			+ "fieldOrArrRef -> expressionWithoutBinaryOp | ( expressionWithoutBinaryOp )\n"
			+

			"expression -> binaryOR\n"
			+ "binaryOR -> binaryOR || binaryAND | binaryAND\n"
			+ "binaryAND -> binaryAND && binaryEQ | binaryEQ\n"
			+ "binaryEQ -> binaryEQ == binaryREL | binaryEQ != binaryREL | binaryREL\n"
			+ "binaryREL -> binaryREL < binaryNonPrecedenceOP | binaryREL > binaryNonPrecedenceOP | binaryREL <= binaryNonPrecedenceOP | binaryREL >= binaryNonPrecedenceOP | binaryNonPrecedenceOP\n"
			+ "binaryNonPrecedenceOP -> binaryNonPrecedenceOP + binaryPrecedenceOP | binaryNonPrecedenceOP - binaryPrecedenceOP | binaryPrecedenceOP\n"
			+ "binaryPrecedenceOP -> binaryPrecedenceOP * expressionUnary | binaryPrecedenceOP / expressionUnary | binaryPrecedenceOP % expressionUnary | expressionUnary\n"
			+

			"expressionUnary -> - expressionUnary | ! expressionUnary | expressionNew\n"
			+

			"expressionNew -> new CLASS_ID ( ) | new type [ expression ] | expressionWithoutBinaryOp\n"
			+

			"retVal -> | expression\n"
			+ "literal -> INTEGER | STRING | true | false | null\n"
			+

			"myWhile -> while ( expression ) statement\n"
			+

			"methodCall -> staticMethodCall | virtualMethodCall\n"
			+ "staticMethodCall -> CLASS_ID . ID ( staticCallExpression )\n"
			+ "staticCallExpression -> | expression optionalCallExpression\n"
			+ "optionalCallExpression -> | , expression optionalCallExpression\n"
			+ "virtualMethodCall -> virtualCallExpression ID ( staticCallExpression )\n"
			+ "virtualCallExpression -> | expressionNew .\n"
			+

			"topLevelIf -> innerIfOptionForNoIf | innerIf\n"
			+ "innerIf -> if ( expression ) topLevelIf | if ( expression ) innerIfOptionForNoIf else innerIf\n"
			+ "innerIfOptionForNoIf -> if ( expression ) innerIfOptionForNoIf else innerIfOptionForNoIf | statementWithoutIfDec\n"
			+ "innerInnerIfOptionForNoIf -> innerIfOptionForNoIf | statementDecl\n";

	private Grammar grammar;

	public Parser(boolean isLibGrammar) {
		if (isLibGrammar) {
			grammar = new Grammar(libGrammar);
		} else {
			grammar = new Grammar(nonLibGrammar);
		}

	}

	/**
	 * initializes the root and prints the AST
	 * 
	 * @param tokens
	 * @return
	 */
	public Node process(List<Token> tokens) {
		Node root = makeAST(ConvertTokensToTree(tokens));
		return root;
	}

	/**
	 * 
	 * @param tokens
	 * @return output tree created by the gearly.jar EarlyParser
	 * 
	 *         note: this is not the .ast output!!!
	 */
	private fun.parser.Tree ConvertTokensToTree(Iterable<Token> tokens) {
		EarleyParser ep = new EarleyParser(tokens, grammar);
		List<EarleyState> statesList = ep.getCompletedParses();

		if (statesList.isEmpty()) {
			EarleyParser.PostMortem earleyError = ep.diagnoseError();
			Token problematicToken = (Token) (earleyError.token);
			String[] expectedVal = earleyError.expecting.toArray(new String[0]);
			Arrays.sort(expectedVal, new Comparator<String>() {
				// comparator implementation for the error printing by ASCII
				// value
				public int compare(String str1, String str2) {
					String string = "";
					if (str1.length() <= str2.length()) {
						string = str1;
					} else {
						string = str2;
					}
					for (int i = 0; i < string.length(); i++) {
						if ((int) str1.charAt(i) < (int) str2.charAt(i)) {
							return -1;
						}
						if ((int) str1.charAt(i) > (int) str2.charAt(i)) {
							return 1;
						}
					}
					if (string.equals(str1)) {
						return -1;
					} else {
						return 1;
					}
				}
			});
			String errorPosition = "";
			String errorMessage = "";
			if (problematicToken == null) {
				errorPosition = "at end of input";
			} else {
				errorPosition = problematicToken.line + ":"
						+ problematicToken.column;
			}

			if (problematicToken == null) {
				errorMessage = "";
			} else {
				errorMessage = ", but found '" + problematicToken.tag + "'";
			}

			System.out.print(errorPosition + " : syntax error; expected '"
					+ expectedVal[0] + "'");
			for (int i = 1; i < expectedVal.length; i++) {
				System.out.print(" or '" + expectedVal[i] + "'");
			}
			System.out.println(errorMessage);
			System.exit(0);
		}

		else if (statesList.size() > 1) {
			throw new Error("the given grammer has some ambiguity!");
		}

		// if statesList.size() == 1
		return statesList.get(0).parseTree();
	}

	/**
	 * 
	 * @param tokenTree
	 * @return abstract syntax tree, using switch-case
	 */
	private Node makeAST(fun.parser.Tree tokenTree) {
		Word word = tokenTree.root;
		fun.parser.Tree[] subtreeArr = tokenTree.subtrees
				.toArray(new fun.parser.Tree[0]);

		switch (word.tag) {

		// the "start" symbol
		case "S":
			return makeAST(subtreeArr[0]);

			// a class
		case "classDecl":
			String className = ((Token) (subtreeArr[1].root)).value;
			int classLine = ((Token) (subtreeArr[1].root)).line;
			List<DeclMethod> classMethods = new ArrayList<DeclMethod>();
			List<DeclField> classFields = new ArrayList<DeclField>();
			addClassFieldsAndMethods(subtreeArr[3], classFields, classMethods);
			DeclClass retClass = new DeclClass(classLine, className,
					classFields, classMethods);
			return retClass;

			// class which extends another class
		case "classDeclExtendsSuperClass":
			String extendedClassName = ((Token) (subtreeArr[1].root)).value;
			String superClass = ((Token) (subtreeArr[3].root)).value;
			int extendedClassLine = ((Token) (subtreeArr[1].root)).line;
			List<DeclMethod> extendedClassMethods = new ArrayList<DeclMethod>();
			List<DeclField> extendedClassFields = new ArrayList<DeclField>();
			addClassFieldsAndMethods(subtreeArr[5], extendedClassFields,
					extendedClassMethods);
			DeclClass retExtendedClass = new DeclClass(extendedClassLine,
					extendedClassName, superClass, extendedClassFields,
					extendedClassMethods);
			return retExtendedClass;

			// library-type
		case "icLibGrammar":
			// verify legal library class name
			if (!(((Token) (subtreeArr[1].root)).value.compareTo("Library") == 0)) {
				throw new Error("illegal name "
						+ (subtreeArr[1].root).toString() + " for Library");
			}
			List<DeclClass> libClass = new ArrayList<DeclClass>();
			libClass.add(new DeclClass(((Token) (subtreeArr[0].root)).line,
					"Library", null, getLibraryMethodsList(subtreeArr[3])));
			return libClass.get(0);

			// a program, using recursion for inner classes and methods if any
		case "program":
			List<DeclClass> classList = new ArrayList<DeclClass>();
			if (subtreeArr.length > 0) {
				classList.add((DeclClass) makeAST(subtreeArr[0]));
			}
			if (subtreeArr.length > 1) {
				Program tempProg = (Program) makeAST(subtreeArr[1]);
				List<DeclClass> tempClassList = tempProg.getClasses();
				for (DeclClass classObj : tempClassList) {
					classList.add(classObj);
				}
			}

			Program program = new Program(classList);
			return program;

		default:
			throw new Error("failed while creating .ast; word.tag is "
					+ word.tag);
		}
	}

	/**
	 * adds both methods and fields to the relevant subtree "tree"
	 * 
	 * @param tree
	 * @param classFields
	 * @param classMethods
	 */
	private void addClassFieldsAndMethods(fun.parser.Tree tree,
			List<DeclField> classFields, List<DeclMethod> classMethods) {
		fun.parser.Tree[] subtreesArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		if (subtreesArr.length == 0) {
			return;
		}
		if (subtreesArr[0].root.tag.compareTo("fields") == 0) {
			classFields.addAll(getClassFieldsList(subtreesArr[0], null));
		} else {
			classMethods.addAll(getClassMethodsList(subtreesArr[0]));
		}

		addClassFieldsAndMethods(subtreesArr[1], classFields, classMethods);

	}

	/**
	 * 
	 * @param tree
	 * @param type
	 * @return list of fields to be added using "addClassFieldsAndMethods"
	 */

	private List<DeclField> getClassFieldsList(fun.parser.Tree tree, Type type) {
		List<DeclField> fields = new ArrayList<DeclField>();
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		Type fieldType = null;
		String fieldName = null;
		if (tree.root.tag.compareTo("fields") == 0) {
			if (subtreeArr.length == 0) {
				return fields;
			}

			fieldType = getType(subtreeArr[0]);
			fieldName = ((Token) (subtreeArr[1].root)).value;
			fields.add(new DeclField(fieldType, fieldName));

			if (subtreeArr.length > 0) {
				fields.addAll(getClassFieldsList(subtreeArr[2], fieldType));
			}
		} else if (tree.root.tag.compareTo("optionalFields") == 0) {
			if (subtreeArr.length == 0) {
				return fields;
			}
			fieldName = ((Token) (subtreeArr[1].root)).value;
			fields.add(new DeclField((Type) type, fieldName));
			if (subtreeArr.length > 0) {
				fields.addAll(getClassFieldsList(subtreeArr[2], type));
			}
		}
		return fields;
	}

	/**
	 * 
	 * @param tree
	 * @return list of methods to be added using "addClassFieldsAndMethods"
	 */
	private List<DeclMethod> getClassMethodsList(fun.parser.Tree tree) {
		boolean isStaticMethod = false;
		List<DeclMethod> methodList = new ArrayList<DeclMethod>();
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		if (subtreeArr.length == 0) {
			return methodList;
		}
		isStaticMethod = subtreeArr[0].subtrees.toArray(new fun.parser.Tree[0]).length > 0;
		Type methodType = getMethodRetType(subtreeArr[1]);
		String methodName = ((Token) (subtreeArr[2].root)).value;
		List<Parameter> methodFormals = getMethodFormals(subtreeArr[4]);
		List<Statement> methodStatements = getMethodStatementsList(subtreeArr[7]);
		if (!isStaticMethod) {
			methodList.add(new DeclVirtualMethod(methodType, methodName,
					methodFormals, methodStatements));
		} else {
			methodList.add(new DeclStaticMethod(methodType, methodName,
					methodFormals, methodStatements));
		}
		return methodList;
	}

	/**
	 * 
	 * @param tree
	 * @return list of methods declared at the input library
	 */
	private List<DeclMethod> getLibraryMethodsList(fun.parser.Tree tree) {
		List<DeclMethod> methods = new ArrayList<DeclMethod>();
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		if (subtreeArr.length != 0) {
			if (tree.root.tag.compareTo("libraryMethod") == 0) {
				methods.addAll(getLibraryMethodsList(subtreeArr[0]));
				methods.addAll(getLibraryMethodsList(subtreeArr[1]));
			} else {
				List<Parameter> formals = getMethodFormals(subtreeArr[4]);
				methods.add(new DeclLibraryMethod(
						getMethodRetType(subtreeArr[1]),
						((Token) (subtreeArr[2].root)).value, formals));
			}
		}
		return methods;
	}

	/**
	 * 
	 * @param tree
	 * @return gets the statements list for "getClassMethodsList"
	 */
	private List<Statement> getMethodStatementsList(fun.parser.Tree tree) {
		List<Statement> statementList = new ArrayList<Statement>();
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		if (subtreeArr.length != 0) {
			statementList.add(processStatement(subtreeArr[0]));
			statementList.addAll(getMethodStatementsList(subtreeArr[1]));
		}
		return statementList;
	}

	/**
	 * 
	 * @param tree
	 * @return processed expression list
	 */
	private List<Expression> getExpressionsList(fun.parser.Tree tree) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		List<Expression> expressionList = new ArrayList<Expression>();
		if (tree.root.tag.compareTo("optionalCallExpression") == 0) {
			if (subtreeArr.length != 0) {
				expressionList.add(processExpression(subtreeArr[1]));
				expressionList.addAll(getExpressionsList(subtreeArr[2]));
			}
		} else {
			if (subtreeArr.length != 0) {
				expressionList.add(processExpression(subtreeArr[0]));
				expressionList.addAll(getExpressionsList(subtreeArr[1]));
			}
		}
		return expressionList;
	}

	/**
	 * 
	 * @param t
	 * @return t's IC type
	 */
	private Type getType(fun.parser.Tree t) {
		fun.parser.Tree[] subtreeArr = t.subtrees
				.toArray(new fun.parser.Tree[0]);
		switch (subtreeArr[0].root.tag) {
		case "void":
			return new PrimitiveType(((Token) (subtreeArr[0].root)).line,
					PrimitiveType.DataType.VOID);
		case "boolean":
			return new PrimitiveType(((Token) (subtreeArr[0].root)).line,
					PrimitiveType.DataType.BOOLEAN);
		case "int":
			return new PrimitiveType(((Token) (subtreeArr[0].root)).line,
					PrimitiveType.DataType.INT);
		case "string":
			return new PrimitiveType(((Token) (subtreeArr[0].root)).line,
					PrimitiveType.DataType.STRING);
		case "CLASS_ID":
			return new ClassType(((Token) (subtreeArr[0].root)).line,
					((Token) (subtreeArr[0].root)).value);

		case "type":
		case "typeLib":
			Type tmp = getType(subtreeArr[0]);
			tmp.incrementDimension();
			return tmp;
		}
		throw new Error("unknown type!");
	}

	/**
	 * 
	 * @param tree
	 * @return the method's returned value type (from its signature)
	 */
	private Type getMethodRetType(fun.parser.Tree tree) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		if (subtreeArr[0].root.tag.compareTo("void") == 0) {
			return new PrimitiveType(((Token) (subtreeArr[0].root)).line,
					PrimitiveType.DataType.VOID);
		}
		return getType(subtreeArr[0]);
	}

	/**
	 * 
	 * @param tree
	 * @return a Statement, processed with respect to the grammar
	 */
	private Statement processStatement(fun.parser.Tree tree) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		switch (subtreeArr[0].root.tag) {
		case "methodCall":
			return new StmtCall(processCall(subtreeArr[0]));
		case "innerIfOptionForNoIf":
		case "innerIf":
			return processIf(subtreeArr[0]);
		case "innerInnerIfOptionForNoIf":
		case "statementWithoutIfDec":
		case "statementDecl":
			return processStatement(subtreeArr[0]);
		case "type":
			int lineNum = ((Token) (subtreeArr[1].root)).line;
			Type type = getType(subtreeArr[0]);
			String identifier = ((Token) (subtreeArr[1].root)).value;
			Expression local_init_value = processInit(subtreeArr[2]);
			if (local_init_value != null) {
				return new LocalVariable(lineNum, type, identifier,
						local_init_value);
			}
			return new LocalVariable(lineNum, type, identifier);
		case "refToValue":
			Ref r = (Ref) processFieldOrVar(subtreeArr[0]);
			Expression assment = processExpression(subtreeArr[2]);
			return new StmtAssignment(r, assment);
		case "myWhile":
			return processWhile(subtreeArr[0]);
		case "break":
			return new StmtBreak(((Token) (subtreeArr[0].root)).line);
		case "continue":
			return new StmtContinue(((Token) (subtreeArr[0].root)).line);
		case "{":
			return new StmtBlock(((Token) (subtreeArr[0].root)).line,
					getMethodStatementsList(subtreeArr[1]));
		case "return":
			fun.parser.Tree[] rets = subtreeArr[1].subtrees
					.toArray(new fun.parser.Tree[0]);
			if (rets.length == 0)
				return new StmtReturn(((Token) (subtreeArr[0].root)).line);
			return new StmtReturn(((Token) (subtreeArr[0].root)).line,
					processExpression(rets[0]));
		}
		return null;
	}

	/***
	 * 
	 * @param tree
	 * @return a Call object - either virtual or static
	 */
	private Call processCall(fun.parser.Tree tree) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		if (tree.root.tag.compareTo("methodCall") == 0) {
			return processCall(subtreeArr[0]);
		}
		int line = ((Token) (subtreeArr[1].root)).line;
		switch (tree.root.tag) {
		case "virtualMethodCall":
			return new VirtualCall(line, processExpression(subtreeArr[0]),
					((Token) (subtreeArr[1].root)).value,
					getExpressionsList(subtreeArr[3]));
		case "staticMethodCall":
			return new StaticCall(line, ((Token) (subtreeArr[0].root)).value,
					((Token) (subtreeArr[2].root)).value,
					getExpressionsList(subtreeArr[4]));
		}
		return null;
	}

	/**
	 * process various if variations
	 * 
	 * @param tree
	 * @return processed if Statement
	 */
	private Statement processIf(fun.parser.Tree tree) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		Expression condition;
		Statement operation;
		switch (tree.root.tag) {
		case "topLevelIf":
			return processIf(subtreeArr[0]);
		case "innerIfOptionForNoIf":
			if (subtreeArr.length == 1) {
				return processStatement(subtreeArr[0]);
			}
			condition = processExpression(subtreeArr[2]);
			operation = processIf(subtreeArr[4]);
			return new StmtIf(condition, operation, processIf(subtreeArr[6]));
		case "innerIf":
			condition = processExpression(subtreeArr[2]);
			operation = processIf(subtreeArr[4]);
			if (subtreeArr.length == 7) {
				return new StmtIf(condition, operation,
						processIf(subtreeArr[6]));
			}
			return new StmtIf(condition, operation);
		case "statement":
			return processStatement(tree);
		}
		return null;
	}

	/**
	 * 
	 * @param tree
	 * @return processed while Statement
	 */
	private Statement processWhile(fun.parser.Tree tree) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		return new StmtWhile(processExpression(subtreeArr[2]),
				processStatement(subtreeArr[4]));
	}

	/**
	 * 
	 * @param tree
	 * @return processed Expression, neglecting unary "-"
	 */
	private Expression processExpression(fun.parser.Tree tree) {
		return processExpression(tree, false);
	}

	/**
	 * 
	 * @param tree
	 * @return processed Expression, with possible unary "-"
	 */
	private Expression processExpression(fun.parser.Tree tree,
			boolean hasUnaryMinus) {
		fun.parser.Tree[] s = tree.subtrees.toArray(new fun.parser.Tree[0]);
		if (tree.root.tag.compareTo("virtualCallExpression") == 0) {
			if (s.length == 0) {
				return null;
			}
			return processExpression(s[0]);
		} else if (tree.root.tag.compareTo("fieldOrArrRef") == 0) {
			if (s.length == 1) {
				return processExpWithoutBinOp(s[0]);
			}
			return processExpWithoutBinOp(s[1]);
		}
		switch (s[0].root.tag) {
		case "binaryOR":
		case "binaryAND":
		case "binaryEQ":
		case "binaryREL":
		case "binaryNonPrecedenceOP":
		case "binaryPrecedenceOP":
			if (s.length == 1)
				return processExpression(s[0]);
			return processBinaryOp(s[0], s[1], s[2]);
		case "expressionUnary":
		case "expressionNew":
			return processExpression(s[0], hasUnaryMinus);
		case "-":
			Expression next = processExpression(s[1], true);
			String string = "";
			if (next instanceof Literal
					&& ((Literal) (next)).getType() == PrimitiveType.DataType.INT) {
				string = ((Literal) (next)).getValue().toString();
				return new Literal(((Token) (s[0].root)).line,
						PrimitiveType.DataType.INT, "-" + string);
			} else {
				return processUnaryOp(s[0], s[1]);
			}
		case "!":
			return processUnaryOp(s[0], s[1]);
		case "expressionWithoutBinaryOp":
			return processExpWithoutBinOp(s[0], hasUnaryMinus);
		case "new":
			return processNewExpression(tree);
		}
		return null;
	}

	/**
	 * 
	 * @param t
	 * @return processed New expression
	 */
	private New processNewExpression(fun.parser.Tree t) {
		fun.parser.Tree[] s = t.subtrees.toArray(new fun.parser.Tree[0]);
		New newExpr = null;
		if (s[1].root.tag.compareTo("CLASS_ID") == 0) {
			newExpr = new NewInstance(((Token) (s[1].root)).line,
					((Token) (s[1].root)).value);
		} else {
			newExpr = new NewArray(getType(s[1]), processExpression(s[3]));
		}
		return newExpr;
	}

	/**
	 * 
	 * @param tree
	 * @return processed expression that has no binary operations within
	 */
	private Expression processExpWithoutBinOp(fun.parser.Tree tree) {
		return processExpWithoutBinOp(tree, false);
	}

	/**
	 * 
	 * @param tree
	 * @return processed expression with possible binary operations within
	 */
	private Expression processExpWithoutBinOp(fun.parser.Tree tree,
			boolean hasUnaryMinus) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		switch (subtreeArr[0].root.tag) {
		case "methodCall":
			return processCall(subtreeArr[0]);
		case "expressionWithoutBinaryOp":
			return processExpWithoutBinOp(subtreeArr[0]);
		case "refToValue":
			return processFieldOrVar(subtreeArr[0]);
		case "fieldOrArrRef":
			int line = ((Token) (subtreeArr[1].root)).line;
			fun.parser.Tree[] tempArr = subtreeArr[0].subtrees
					.toArray(new fun.parser.Tree[0]);
			return new Length(line, processExpWithoutBinOp(tempArr[0]));
		case "literal":
			return processLiteral(subtreeArr[0], hasUnaryMinus);
		case "this":
			return new This(((Token) (subtreeArr[0].root)).line);
		case "(":
			return processExpression(subtreeArr[1]);

		}
		return null;
	}

	/**
	 * 
	 * @param tree
	 * @param hasUnaryMinus
	 * @return processed literal with possible unary "-"
	 */
	private Literal processLiteral(fun.parser.Tree tree, boolean hasUnaryMinus) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		PrimitiveType.DataType type = null;
		String value = ((Token) (subtreeArr[0].root)).value;
		switch (subtreeArr[0].root.tag) {
		case "INTEGER":
			@SuppressWarnings("unused")
			int integer;
			try {
				if (!hasUnaryMinus) {
					integer = Integer.parseInt(value);
				} else {
					integer = Integer.parseInt("-".concat(value));
				}
			} catch (NumberFormatException e) {
				System.out.println(((Token) (subtreeArr[0].root)).line + ":"
						+ ((Token) (subtreeArr[0].root)).column
						+ " : syntax error; numeric literal out of range: "
						+ value);
				System.exit(0);
			}
			type = PrimitiveType.DataType.INT;
			break;
		case "STRING":
			type = PrimitiveType.DataType.STRING;
			String string = "";

			// remove buggy escape-chars
			for (int i = 1; i < value.length() - 1; i++) {
				if (value.charAt(i) == '\\') {
					switch (value.charAt(i + 1)) {
					case '\\':
						string += ("\\");
						break;
					case '"':
						string += ('\"');
						break;
					case 'n':
						string += ("\n");
						break;
					case 't':
						string += ("\t");
						break;
					}
					i++;
				} else {
					string += value.charAt(i);
				}
			}
			value = string;
			break;
		case "true":
		case "false":
			type = PrimitiveType.DataType.BOOLEAN;
			break;
		case "null":
			type = PrimitiveType.DataType.VOID;
			break;
		}

		return new Literal(((Token) (subtreeArr[0].root)).line, type, value);
	}

	/**
	 * 
	 * @param tree
	 * @return a reference to field, array value or identifier
	 */
	private Ref processFieldOrVar(fun.parser.Tree tree) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		switch (subtreeArr[0].root.tag) {
		case "fieldOrArrRef":
			if (subtreeArr.length == 3) {
				Token field = ((Token) (subtreeArr[2].root));
				return new RefField(field.line,
						processExpression(subtreeArr[0]), field.value);
			} else {
				return new RefArrayElement(processExpression(subtreeArr[0]),
						processExpression(subtreeArr[2]));
			}
		case "ID":
			Token var = ((Token) (subtreeArr[0].root));
			return new RefVariable(var.line, var.value);
		}
		return null;
	}

	/**
	 * 
	 * @param tree
	 * @return
	 */
	private Expression processInit(fun.parser.Tree tree) {
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		if (subtreeArr.length == 0) {
			return null;
		} else {
			return processExpression(subtreeArr[1]);
		}
	}

	/**
	 * 
	 * @param tree
	 * @return a list of the methods formal arguments
	 */
	private List<Parameter> getMethodFormals(fun.parser.Tree tree) {
		List<Parameter> formalsList = new ArrayList<Parameter>();
		Type formalType = null;
		String formalName = null;
		fun.parser.Tree[] subtreeArr = tree.subtrees
				.toArray(new fun.parser.Tree[0]);
		if (subtreeArr.length == 0) {
			return formalsList;
		}
		if (tree.root.tag.compareTo("formalArgs") == 0
				|| tree.root.tag.compareTo("formalArgsLib") == 0) {
			formalName = ((Token) (subtreeArr[1].root)).value;
			formalType = getType(subtreeArr[0]);
			formalsList.add(new Parameter(formalType, formalName));
			if (subtreeArr.length > 0) {
				formalsList.addAll(getMethodFormals(subtreeArr[2]));
			}
		} else if (tree.root.tag.compareTo("optionalFormalArgs") == 0
				|| tree.root.tag.compareTo("optionalFormalArgsLib") == 0) {
			formalName = ((Token) (subtreeArr[2].root)).value;
			formalType = getType(subtreeArr[1]);
			formalsList.add(new Parameter(formalType, formalName));
			if (subtreeArr.length > 0) {
				formalsList.addAll(getMethodFormals(subtreeArr[3]));
			}
		}
		return formalsList;
	}

	/**
	 * 
	 * @param op
	 * @param operand
	 * @return processed unary operation
	 */
	private UnaryOp processUnaryOp(fun.parser.Tree op, fun.parser.Tree operand) {
		int line = ((Token) (op.root)).line;
		UnaryOp.UnaryOps operator;
		if (op.root.tag.compareTo("-") == 0) {
			operator = UnaryOp.UnaryOps.UMINUS;
			return new UnaryOp(line, operator, processExpression(operand, true));
		} else
			operator = UnaryOp.UnaryOps.LNEG;
		return new UnaryOp(line, operator, processExpression(operand, false));
	}

	/**
	 * 
	 * @param lhsOperand
	 * @param op
	 * @param rhsOperand
	 * @return processed binary operation
	 */
	private BinaryOp processBinaryOp(fun.parser.Tree lhsOperand,
			fun.parser.Tree op, fun.parser.Tree rhsOperand) {
		int line = ((Token) (op.root)).line;
		BinaryOp.BinaryOps operator = null;
		switch (op.root.tag) {
		case "&&":
			operator = BinaryOp.BinaryOps.LAND;
			break;
		case "||":
			operator = BinaryOp.BinaryOps.LOR;
			break;
		case "<":
			operator = BinaryOp.BinaryOps.LT;
			break;
		case "<=":
			operator = BinaryOp.BinaryOps.LTE;
			break;
		case ">":
			operator = BinaryOp.BinaryOps.GT;
			break;
		case ">=":
			operator = BinaryOp.BinaryOps.GTE;
			break;
		case "==":
			operator = BinaryOp.BinaryOps.EQUAL;
			break;
		case "!=":
			operator = BinaryOp.BinaryOps.NEQUAL;
			break;
		case "+":
			operator = BinaryOp.BinaryOps.PLUS;
			break;
		case "-":
			operator = BinaryOp.BinaryOps.MINUS;
			break;
		case "*":
			operator = BinaryOp.BinaryOps.MULTIPLY;
			break;
		case "/":
			operator = BinaryOp.BinaryOps.DIVIDE;
			break;
		case "%":
			operator = BinaryOp.BinaryOps.MOD;
			break;
		default:
			throw new Error("unknown binary OP!");
		}
		return new BinaryOp(line, processExpression(lhsOperand), operator,
				processExpression(rhsOperand));
	}
}